/**
 * 暴力匹配
 */
const brute_force = function(text, pattern) {
  for (let i = 0; i < text.length; i++) {
    let flag = 1;
    for (let j = 0; j < pattern.length; j++) {
      // 当前字符可以匹配上
      if(text[i + j] === pattern[j]) continue;
      flag = 0;
      break;
    }
    // 此时，pattern都被匹配上
    if(flag) return i; 
  }
  return -1;
}

/**
 * KMP
 */
function getNext(pattern, next) {
  next[0] = -1;
  // j:  要处理的字符的前一个字符位置, next[j]已经被计算出了
  // pattern[j + 1]: 当前要计算预处理信息的字符

  for (let i = 1, j = -1; i < pattern.length; ++i) {
    while( j != -1 && pattern[j + 1] !== pattern[i]) j = next[j];
    if(pattern[j + 1] === pattern[i]) j += 1;
    // 如果相等，跳到后一位
    next[i] = j;
  }
  return;
}

const kmp = function(text, pattern) {
  // 存放预处理信息，预处理信息为j需要往前跳的下一个位置
  const next = [];
  // 计算预处理信息
  getNext(pattern, next);

  for (let i = 0, j = -1; i < text.length; i++) {
    while(j != -1 && text[i] !== pattern[j + 1]) j = next[j];
    if(text[i] === pattern[j + 1]) j += 1;
    // pattern全部已经匹配完
    if(pattern[j + 1] === undefined) return i - j;
  }
  return -1;
}

/**
 * 预处理信息：标记模板串中每个字符出现的最后位置
 */
const sunday = function(text, pattern) {
  // 假设最多有256个不同字符
  const BASE = 256;
  // 记录每个字符出现的位置
  let last_pos = new Array(BASE);

  // 初始化每个字符出现的位置
  for(let i = 0; i < BASE; i++) last_pos[i] = -1;

  let m; // 模板串的长度
  // 记录每个字符出现的位置
  for (m = 0; m < pattern.length; m++) last_pos[pattern[m].charCodeAt()] = m;

  // text[i + m]: 母串中，下一个需要匹配的字符（模板串后面那个位置）。
  // last_pos[text[i + m].charCodeAt]: 下一个字符在模板串中的位置。
  // m - last_pos[text[i + m].charCodeAt]: 下一个字符在模板串中的倒数位置。
  for(let i = 0; i + m <= text.length; i += (m - last_pos[text[i + m].charCodeAt()])) {
    let flag = 1;
    for (let j = 0; j < pattern.length; j++) {
      if(text[i + j] === pattern[j]) continue;
      flag = 0;
      break;
    }
    if(flag) return i;
  }
  return -1;
}


function test() {
  const cases = [
    ['hello', 'ell'],
    ['hello', 'he'],
    ['hello', 'e'],
    ['hello', 'wor'],
  ]
  cases.forEach(function(ca) {
    let ret = brute_force(ca[0], ca[1])
    console.log('brute_force', ca[0], ca[1], ret);

    let ret2 = kmp(ca[0], ca[1])
    console.log('kmp', ca[0], ca[1], ret2);

    let ret3 = sunday(ca[0], ca[1])
    console.log('sunday', ca[0], ca[1], ret3);
  })
}
test();